package com.ruoxi.blog.test;

import java.util.Arrays;

/**
	* @author YaoXian
	* @title: QuickSort
	* @projectName ruoxi-blog
	* @description: 若兮微服务 - 快速排序
	* @date 2021-03-21 22:08
	*/
public class QuickSort {
		public static void main(String[] args) {
				int [] arr = {-50,2,6,-899,86,44,566,444,222};
				int left = 0;
				int right = arr.length - 1;
				sort(arr,left,right);
				System.out.println(Arrays.toString(arr));
		}
		
		public static void sort(int[] arr,int l,int r){
				int left = l;
				int right = r;
				int middle = arr[(left+right)/2];
				int temp;
				while (left < right) {
						while (arr[left] < middle){
								left++;
						}
						
						while (arr[right] > middle){
								right--;
						}
						
						if (left >= right){
								break;
						}
						
						temp = arr[left];
						arr[left] = arr[right];
						arr[right] = temp;
						
						if (arr[left] == middle){
								right--;
						}
						
						if (arr[right] == middle){
								left++;
						}
						
						if (left == right){
								left++;
								right--;
						}
						// 向左递归
						if (l < right){
								sort(arr,l,right);
						}
						
						// 向右递归
						if (r > left) {
								sort(arr,left,r);
						}
				}
		}
}
